/*
给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。
*/
class Solution {
public:
    string addBinary(string a, string b) {
        int n=a.length();
        int m=b.length();
        int x=max(n,m);
        string s;
        int c=0;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        for(int i=0;i<x;i++){
            if(i>=n){
                if(b[i]=='0'&&c==0){
                    s.push_back('0');
                    c=0;
                }
                else if(b[i]=='0'&&c==1){
                    s.push_back('1');
                    c=0;
                }
                else if(b[i]=='1'&&c==0){
                    s.push_back('1');
                    c=0;
                }
                else if(b[i]=='1'&&c==1){
                    s.push_back('0');
                    c=1;
                }
            }
            else if(i>=m){
                if(a[i]=='0'&&c==0){
                    s.push_back('0');
                    c=0;
                }
                else if(a[i]=='0'&&c==1){
                    s.push_back('1');
                    c=0;
                }
                else if(a[i]=='1'&&c==0){
                    s.push_back('1');
                    c=0;
                }
                else if(a[i]=='1'&&c==1){
                    s.push_back('0');
                    c=1;
                }
            }
            else{
                if(a[i]=='0'&&b[i]=='0'&&c==0){
                    s.push_back('0');
                    c=0;
                }
                else if(a[i]=='0'&&b[i]=='0'&&c==1){
                    s.push_back('1');
                    c=0;
                }
                else if(a[i]=='0'&&b[i]=='1'&&c==0){
                    s.push_back('1');
                    c=0;
                }
                else if(a[i]=='1'&&b[i]=='0'&&c==0){
                    s.push_back('1');
                    c=0;
                }
                else if(a[i]=='0'&&b[i]=='1'&&c==1){
                    s.push_back('0');
                    c=1;
                }
                else if(a[i]=='1'&&b[i]=='0'&&c==1){
                    s.push_back('0');
                    c=1;
                }
                else if(a[i]=='1'&&b[i]=='1'&&c==0){
                    s.push_back('0');
                    c=1;
                }
                else if(a[i]=='1'&&b[i]=='1'&&c==1){
                    s.push_back('1');
                    c=1;
                }
            }
        }
        if(c==1){
            s.push_back('1');
        }
        reverse(s.begin(),s.end());
        return s;
    }
};